1. Field of the Invention
Methods consistent with the present invention relate to broadcast encryption, and more particularly, to hierarchical threshold tree-based broadcast encryption which can improve the performance of a broadcast transmitting system and protect data against collusion attacks by revocators through a hierarchical use of a (t,n)-threshold technique.
2. Description of the Related Art
In general, there are two kinds of encryption systems that are distinguished depending on their encryption key management types: one is a symmetric cipher (or secret key) encryption system and the other is a non-symmetric cipher (or public key) encryption system. The symmetric cipher encryption system is an encryption method that had been mostly used before the public key encryption system came to existence. In the symmetric cipher encryption system, the same key is used for both the encryption and decryption. For example, in the case where a sender converts a plaintext message into a ciphertext through an encryption key and an encryption algorithm, and transmits the ciphertext to a recipient, the recipient may restore the ciphertext back to the original plaintext using a decryption algorithm having the same key used for the encryption algorithm.
In this case, the recipient should safely exchange the encryption key prior to a cryptographic communication. Thus, any third party, who intends to tap into the messages, cannot know the original plaintext unless the third party finds the key used by the sender and the recipient. However, the number of keys that should be managed is increased as the number of sender-recipient parties subject to encryption is increased, from which a number of problems in key management and exchange have arisen.
In comparison to the symmetric cipher encryption system, the non-symmetric cipher encryption system is based on mathematical function. The non-symmetric cipher encryption system has a pair of keys one of which is open to the public so that anyone can use it, and the other of which is secret. Here, the key open to the public is called a public key, and the secret key is called a private key.
In order to communicate between the sender and the recipient using the public key, the sender first encrypts a message with the public key of the recipient and transmits it to the recipient. The recipient obtains the plaintext of the message by decrypting the ciphertext with his/her private key. Even if someone has obtained the ciphertext through a network, the message can be safely transferred because he cannot decrypt the ciphertext without the private key of the recipient. The reason is that the private key is always kept secret by its owner and is not known or transmitted to anyone.
The symmetric cipher is widely used to encrypt/decrypt a broadcast stream because the encryption/decryption using the symmetric cipher can be performed very quickly and the symmetric cipher can be safely transferred through a limited access system that permits an access of privileged users (authorized users) only.
In a data transmission system using general broadcast encryption (BE), contents providers create various beneficial data including audio and video data, and provide the created data to service providers. Then, the service providers broadcast the data to rightful users (e.g., users of mobile digital right management (DRM) networks and smart home DRM networks) who have paid charges for the corresponding data through various kinds of wire/wireless communication networks.
FIG. 1 is a view illustrating a conventional broadcast transmission system. Referring to FIG. 1, a service provider 100 creates a broadcasting message 110 and transmits the message to respective users through various transmission channels 120. At this time, the broadcasting message is transmitted to not only privileged users 130 but also revoked users 140. Accordingly, the service provider 100 encrypts the broadcasting message by assigning individual keys to the users so that only the privileged users (authorized users) 130 can read the transmitted broadcasting messages. In this case, it has become an important issue in the broadcast system to create specified group keys with which only the privileged users (authorized users) 130 can decrypt the encrypted message.
For example, the service provider can transmit data to users' devices such as set-top boxes provided with various satellite receivers via a satellite, and transmit the data to mobile communication terminals through a mobile communication network. Also, the service provider can transmit the data to various terminals of smart home networks through the Internet.
In order to prevent the non-privileged users (unauthorized users) who have not paid the due charges for the corresponding data, the data is encrypted by a BE method.
Security in the encryption/decryption system generally depends on an encryption key management system. In the encryption key management system, an important aspect is how to derive encryption keys. Also, it is important to manage and update the derived encryption keys.
A data transmission method by the public key scheme is a data transmission method that includes key values for rightful users in data to be transmitted from the service provider to the users. That is, the data transmitted by the service provider through broadcast/home network is composed of a header part including authenticated information and an encrypted data part including actual data information. The header part includes a group ID and key value information of the privileged users (authorized users) corresponding to each authorized group so that the data is transmitted only to the users of the authorized group. Therefore, the data is encrypted by Certificate Revocation List (CRL) and Online Certificate Status Protocol (OCSP) including CRL and OCSP information, and the encrypted data is transmitted to the recipients. Then, the privileged users (authorized users) can use the data by confirming their key value information included in the header part of the received data and normally performing an authentication.
In the BE method, the header part includes only the group ID and key value information corresponding to the group. Therefore, the rightful users of the authorized group can normally decrypt the received data using their own group key value.
Another BE method is disclosed in “Broadcast Encryption” by Fiat, et al. (Crypto '93, LINCS vol. 839, pp 480-491, 1994) (hereinafter referred to as “Fiat algorithm”). This method has proposed two basic BE algorithms and an algorithm having an enhanced security against collusion attacks.
Now, the Fiat algorithm will be briefly explained. For the explanation of the Fiat algorithm, some coefficients are defined as follows:
U: Set of users with |U|=n
P: Set of privileged users with |U−P|=r
N: RSA composite
y1, . . . , yn: Distinct primes
usri: A user in U where 1≦i≦n
O: A positive integer satisfying 1≦O≦N
The Fiat algorithm enables a server to create system coefficients N, y1, . . . , yn, O of the defined coefficients, and N, y1, . . . , yn of the defined coefficients to be publicly disclosed to anyone to get access. Also, if user usri subscribes to the service, the server performs the following process:
1. Assign value yi to the users usri.
2. Calculate secret information ui=0yi (mod N) of the user usri.
3. Safely transfer the calculated secret information to the user usri.
Initial setup and user subscription procedure are completed through the above process. Then, if privileged user (authorized user) group P⊂U is given, group key KP for each user is set by Equation (1).
                              K          P                =                              O                                          ∏                                  usr                  ,                                      ∈                    P                                                              ⁢                              y                s                                              ⁢                                          ⁢                      (                          mod              ⁢                                                          ⁢              N                        )                                              (        1        )            
At this time, each user included in P can calculate the group key KP of Equation (1) by Equation (2) using the value ui obtained from the server.
                              K          P                =                              u            i                                          ∏                                  usr                  ,                                      ∈                                          P                      ·                                              (                                                  usr                          i                                                )                                                                                                        ⁢                              y                s                                              ⁢                                          ⁢                      (                          mod              ⁢                                                          ⁢              N                        )                                              (        2        )            
Since non-privileged users (unauthorized users) or revocators have a prime number yi, which is not included in the KP, in the exponent of ui, they cannot calculate the group key KP without removing the prime number yi from the exponent. This calculation is actually impossible due to the problem that ‘the prime factorization of N is hard”. Thus, the BE can be effectively done for the rightful user according to the above-mentioned method.
However, if two users, e.g., usri and usrj, share their secret information each other, serious problems may occur in the security of the Fiat algorithm. That is, since yi and yj are relatively prime, integers “a” and “b” satisfying a condition “ayi+byj=1” can be easily obtained. Then, the two users can obtain the secret information “value O” of the system from Equation (3).uiaujb≡Oayi+byj=O(mod N)  (3)
Therefore, the non-privileged users (unauthorized users) can obtain the group key KP from the “value O” in all cases. That is, if the two users act in collusion to obtain the secret information of the server that broadcasts contents, the security of the system can no longer be assured. The above system, which is secure from one attacker but is not secure from two or more attackers, is called a “1-resilient system.” Although Fiat has proposed a “k-resilient system” based on the 1-resilient system, it is quite inefficient.
The k-resilient system is to remove a certain number of receivers (the number of receivers is “t” at maximum) which attempt to collude with each other. In the system, however, relatively long messages are required, relatively a large number of keys should be stored in the receivers, and each of the receivers should perform one or more decryption operations.
Further, the system does not consider a scenario of a state non-retaining receiver. It is necessary to avoid the difficulty of supposition as to how many receivers will collude with each other. Further, it is necessary to minimize the size of a message and the number of stored keys, and to minimize the decryption operations to be performed by the receivers in order to optimize the performance of the system.
Additionally, other encryption systems like the Fiat system do not provide a scenario of a state non-retaining receiver, and thus they cannot be effectively applied to the protection of contents in a recording medium.